// https://leetcode.cn/problems/unique-substrings-in-wraparound-string/

// 题干：定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：
//      "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
//      给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

// 示例：输入：s = "zab"
//      输出：6

// 碎语：小写字符的范围是97~122
//       去重策略是相同字母结尾的dp值，我们取最大的即可

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int findSubstringInWraproundString(string s)
    {
        // dp[i]表示以i位置的元素为结尾的所有子串里面，有多少个在base中出现过
        int hash[26] = {0};
        int n = s.size(), ret = 0;
        vector<int> dp(n); dp[0] = 1;

        for (int i = 1 ; i < n ; i++){
            int a = static_cast<int>(s[i]) - 97; // a是当前字符
            int b = static_cast<int>(s[i - 1]) - 97; // b是上一个字符

            if (a == (b + 1) % 26) dp[i] = dp[i - 1] + 1;
            else dp[i] = 1;
        }

        for (int i = 0 ; i < n ; i++){
            int ch = s[i] - 'a';
            hash[ch] = max(hash[ch], dp[i]);
        }
        for (int i = 0 ; i < 26 ; i++) ret += hash[i];

        return ret;
    }
};

int main()
{
    Solution sol;
    string s = "zab";

    cout << sol.findSubstringInWraproundString(s) << endl;

    return 0;
}
